Updated at 2021.4.27

Fast Fourier Transform

이 글을 수학으로 배우는 파동의 법칙 이라는 책을 읽고 정리하였다. 이전 글에서 유도한 푸리에 변환 공식은 다음과 같다.

$$\begin{align}G(f) = \int_{-\infty}^{\infty}{f(t)e^{-i 2\pi f t} dt}\end{align}$$

위 식을 이용하여 실제 음성의 파동을 푸리에 변환하기 위해서는 적분을 무한대로 구간에서 해야 하는데, 현실에서는 그렇게 할 수 없다. 일정 시간 간격으로 유한개의 파동값을 읽어서 사용할 수 밖에 없다.

불연속 푸리에 변환

그 일정 시간 간격을 $\tau$ 라고 하고, 읽어낸 값의 개수를 $N$ 이라고 하면, 위의 적분식은 주파수 $f= \frac{n}{\tau N}$ 일때, 위의 수식은 아래와 같이 쓸 수 있다.

$$\begin{align}\red{G(\frac{n}{\tau N}) = \sum_{k=0}^{N-1} \lbrace\tau \cdot f(k\tau) e^{-i 2\pi k \frac{n}{\tau N}} \rbrace}\end{align}$$

위 식을 불연속 푸리에 변환이라고 한다. 위의 식의 문제점은 관찰 구간내에서 최대 $N/2$ 회 진동하는 파동까지만 계산할 수 있다. (참고로, $M$ 번 진동하는 파동은 최소 $2M$ 개의 값을 읽어야 식별 가능 하기 때문임)

예를 들어 0.3초짜리 4000Hz의 음성에서 푸리에 계수 1개를 뽑아내기 위해서는 2400회의 계산이 필요하고

$$\begin{align}\tau = \frac{0.5}{4000} = 1.25e^{-4}\end{align}$$

$$\begin{align}N = \frac{0.3}{\tau} = 2400\end{align}$$

푸리에 계수를 1Hz부터 4000Hz까지 4000개를 계산하려면, $2400\times 4000$ 회의 지수함수 및 곱셈 계산이 필요하다.

계산 횟수 줄이기

설명의 편의를 위해 위의 식에서 $\tau = 1$ 라고 하면,

$$\begin{align}\red{G(n/N) = \sum_{k=0}^{N-1} f(k) W^{nk}}\end{align}$$

여기서,

$$\begin{align}W = e^{ -\frac{i 2\pi}{N}}\end{align}$$

추가로, $N = 8$ 라고 하면,

$$\begin{align}G(n/8) = \sum_{k=0}^{7} f(k) W^{nk}\end{align}$$

$$\begin{align}W = e^{ -\frac{i 2\pi}{8}}\end{align}$$

$W$ 는 회전 연산자라고 할 수 있는데, $N= 8$ 일 때는 $n$ 이 임의의 정수이고, $0 \le k \lt 8$ 에 대해서 아래와 같음을 알 수 있다.

$$\begin{align}W^{k + 8n} = W^{k}\end{align}$$

따라서

$$\begin{align}\begin{split}G(n/8) &= \sum_{k=0}^{N-1} f(k) W^{nk}\\ &=\sum_{k=0}^{\frac{N}{2}-1} f(2k) W^{n2k} + \sum_{k=0}^{\frac{N}{2}-1} f(2k+1) W^{n(2k+1)}\end{split}\end{align}$$

추가로 정리하면,

$$\begin{align}\red{G(n/8) =\sum_{k=0}^{\frac{N}{2}-1} p(k) W^{2nk} + W^n \cdot \sum_{k=0}^{\frac{N}{2}-1} q(k) W^{2nk}}\end{align}$$

여기서 $p(k) = f(2k)$, $q(k) = f(2k+1)$ 이다. 위 식의 장점은 $G(\frac{4+m}{8})$ 를 계산하고자 할 때 $G(\frac{m}{8})$ 을 계산할 때 사용한 값을 그대로 사용할 수 있다는 것이다.

즉 64번의 계산량이 짝수일 때 16번, 홀수 일때 16번 + 4번($W^n$ 을 곱하는 회수)로 총 34번으로 줄어든다.

유사한 절차를 한번 더 진행하면,

$$\begin{align}\begin{split}G(n/8) &= \sum_{k=0}^{\frac{N}{4}-1} a(k) W'^{2nk} + W'^n \cdot \sum_{k=0}^{\frac{N}{4}-1} b(k) W'^{2nk}\\ &+ W^n \Big( \sum_{k=0}^{\frac{N}{4}-1} c(k) W'^{2nk} + W'^n \cdot \sum_{k=0}^{\frac{N}{4}-1} d(k) W'^{2nk}\Big) \end{split}\end{align}$$

여기서 $a(k) = p(2k)$, $b(k) = p(2k+1)$, $c(k) = q(2k)$, $d(k) = q(2k+1)$, $W' = W^2$ 이다.

계산회수는 16번에, $W^n$ 곱하기 회수 4번, $W'^n$ 곱하기 회수 4번으로 총 24회로 줄어든다.

위와 같은 알고리즘을 활용하여, $N=8$ 일때는 $2^3$ 으로 2번의 절차를 통해 회수를 줄였는데, 일반적으로 $N=1024 = 2^{10}$ 개의 점을 취하면, 9번의 절차를 통해 계산 회수를 획기적으로 줄일 수 있다.

이 알고리즘을 FFT (Fast Fourier Transform) 이라고 한다.

Most Popular #3

Recent #3